// LCP 08. 剧情触发时间

//!生产每天的结果进行查找
function getTriggerTime(increase: number[][], requirements: number[][]): number[] {
    let p = [[0,0,0]]
    let cur = [0,0,0]
    const len = requirements.length
    let ans = []
    //把每天的都给枚举出来，肯定是个有序的，就可以折半查找
    for(let it of increase){
        cur = [cur[0]+it[0],cur[1]+it[1],cur[2]+it[2]]
        p.push(cur)
    }
    for(let it of requirements){
        let low = 0
        let high = p.length-1
        let res = -1
        while(low<=high){
            let mid = Math.floor((low+high)/2)
            if(p[mid][0]>=it[0]&&p[mid][1]>=it[1]&&p[mid][2]>=it[2]){
                high = mid -1
                res = mid
            }else{
                low = mid+1
            }
        }
        ans.push(res)
    }
    return ans 
};



//! 对单个属性进行看待 最终结果就是一个requirement单个属性被激活的的最大值
//! 因为没办法对整个数组进行排序，只能考虑单个属性
function getTriggerTime_2(increase: number[][], requirements: number[][]): number[] {
    //又慢，又费空间，代码又长
    class Status{
        value:number
        index:number
        constructor(v:number,i:number){
            this.value = v
            this.index = i
        }
    }

    let ans0:number[] = new Array(requirements.length)
    ans0.fill(-1)
    let s0:Status[] = []
    //
    let ans1:number[] = new Array(requirements.length)
    ans1.fill(-1)
    let s1:Status[] = []
    //
    let ans2:number[] = new Array(requirements.length)
    ans2.fill(-1)
    let s2:Status[] = []

    for(let i=0;i<requirements.length;i++){
        s0.push(new Status(requirements[i][0],i))
        s1.push(new Status(requirements[i][1],i))
        s2.push(new Status(requirements[i][2],i))
    }
    s0.sort((a,b)=>a.value-b.value)
    s1.sort((a,b)=>a.value-b.value)
    s2.sort((a,b)=>a.value-b.value)
    //找到0的开始点
    let start0 = 0
    for(let i=0;i<s0.length;i++){
        if(s0[i].value==0) {
            ans0[s0[i].index] = 0
            start0++
        }else{
            break
        }
    }

    //找到1的开始点
    let start1 = 0
    for(let i=0;i<s1.length;i++){
        if(s1[i].value==0) {
            ans1[s1[i].index] = 0
            start1++
        }else{
            break
        }
    }
    
    //找到1的开始点
    let start2 = 0
    for(let i=0;i<s2.length;i++){
        if(s2[i].value==0) {
            ans2[s2[i].index] = 0
            start2++
        }else{
            break
        }
    }

    let cur0 = 0 
    let cur1 = 0 
    let cur2 = 0 

    for(let i=0;i<increase.length;i++){
        cur0 += increase[i][0]
        cur1 += increase[i][1]
        cur2 += increase[i][2]
        //第0个属性
        for(let j= start0;j<s0.length;j++){
            if(s0[j].value<=cur0) {
                ans0[s0[j].index] = i+1
                start0++
            }else{
                break
            }   
        }
        //第1个属性
        for(let j= start1;j<s1.length;j++){
            if(s1[j].value<=cur1) {
                ans1[s1[j].index] = i+1
                start1++
            }else{
                break
            }   
        }
        //第二个属性
        for(let j= start2;j<s2.length;j++){
            if(s2[j].value<=cur2) {
                ans2[s2[j].index] = i+1
                start2++
            }else{
                break
            }   
        }
    }
    let ans = []
    for(let i=0;i<requirements.length;i++){
        if(ans0[i]==-1||ans1[i]==-1||ans2[i]==-1) ans.push(-1)
        else ans.push(Math.max(ans0[i],ans1[i],ans2[i]))
    }
    return ans
}
const ans = getTriggerTime_2([[6,3,4],[6,7,2]],
    [[0,13,14],[0,5,5],[0,4,18],[4,3,4]])
console.log(ans)